package club.xiaojiawei.array;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/19 22:50
 * @question 209.长度最小的子数组
 * @description 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 */
public class SonArrForMin209 {

    public static void main(String[] args) {
        int[] arr={1,1,1,4,6,1,2,1,1};
        System.out.println(minSubArrayLen(213, arr));
        System.out.println(minSubArrayLen1(9, arr));
    }

    /**
     * 窗口滑动法
     * @param target
     * @param nums
     * @return
     */
    public static int minSubArrayLen(int target, int[] nums) {
        int count = 0;
        int start = 0;
        int end = 0;
        int size =  Integer.MAX_VALUE;
        while (end < nums.length) {
            if (nums[end] > target){
                return 1;
            }else {
                count += nums[end];
                while (count >= target){
                    size = Math.min(size, end - start + 1);
                    count -= nums[start];
                    start++;
                }
                Arrays.binarySearch(nums,target);
                end++;
            }
        }
        return size == Integer.MAX_VALUE ? 0 : size;
    }

    /**
     * 官方 - 前缀和 + 二分查找
     * @param s
     * @param nums
     * @return
     */
    public static int minSubArrayLen1(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        int[] sums = new int[n + 1];
        // 为了方便计算，令 size = n + 1
        // sums[0] = 0 意味着前 0 个元素的前缀和为 0
        // sums[1] = A[0] 前 1 个元素的前缀和为 A[0]
        // 以此类推
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        for (int i = 1; i <= n; i++) {
            int target = s + sums[i - 1];
            int bound = Arrays.binarySearch(sums, target);
            if (bound < 0) {
                bound = -bound - 1;
            }
            if (bound <= n) {
                ans = Math.min(ans, bound - (i - 1));
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
